package medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 9. 组合总和
 * 创建时间：2024-04-20 20:40
 * 地址：https://leetcode.cn/problems/combination-sum/description/
 */
public class 组合总和_39 {
    /**
     * 方法一：选与不选
     * 回溯算法，子集型回溯
     * 用 dfs(i,left) 来回溯，设当前枚举到 candidates[i]，剩余要选的元素之和为 left，按照选或不选分类讨论：
     *  ·不选：递归到 dfs(i+1,left)
     *  ·选：递归到 dfs(i,left−candidates[i])。注意 i 不变，表示在下次递归中可以继续选 candidates[i]
     * 注：这个思路类似 完全背包
     *
     * 如果递归中发现 left=0 则说明找到了一个合法组合，复制一份 path 加入答案
     * 递归边界：如果 i=n 或者 left<0 则返回
     * 递归入口：dfs(0,target)
     */
    static class Solution {
        List<List<Integer>> rsl = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            dfs(candidates, target, 0, new ArrayList<>());
            return rsl;
        }

        void dfs(int[] candidates, int left, int i, List<Integer> path) {
            if (left == 0) {
                rsl.add(new ArrayList<>(path));
                return;
            }

            if (i == candidates.length || left < 0) {
                return;
            }

            // 不选
            dfs(candidates, left, i + 1, path);

            // 选
            path.add(candidates[i]);
            dfs(candidates, left - candidates[i], i, path);
            path.remove(path.size() - 1);
        }

    }

    /**
     * 方法二：枚举（个人想法，但是没写出来，抄灵茶山艾府衙的）
     * 同样用 dfs(i,left) 来回溯，设当前枚举到 candidates[i]，剩余要选的元素之和为 left，考虑枚举下个元素是谁：
     * 在 [i,n−1] 中枚举要填在 path 中的元素 candidates[j]，然后递归到 dfs(j,left−candidates[j])。
     * 注意这里是递归到不是 j+1，表示 candidates[j] 可以重复选取。
     */
    static class Solution2 {
        List<List<Integer>> rsl = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            dfs(candidates, target, 0, new ArrayList<>());
            return rsl;
        }

        void dfs(int[] candidates, int left, int i, List<Integer> path) {
            if (left == 0) {
                rsl.add(new ArrayList<>(path));
                return;
            }

            if (left < candidates[i]) {
                return;
            }

            for (int j = i; j < candidates.length; j++) {
                path.add(candidates[j]);
                dfs(candidates, left - candidates[j], j, path);
                path.remove(path.size() - 1);
            }

        }
    }

}
